package week_03;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Collectors;

/**
 * 51. N 皇后
 * n皇后问题 研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 给你一个整数 n ，返回所有不同的n皇后问题 的解决方案。
 * <p>
 * 每一种解法包含一个不同的n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * <p>
 * 示例 1：
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 * <p>
 * 示例 2：
 * <p>
 * 输入：n = 1
 * 输出：[["Q"]]
 *
 * 思路：统计所有组合在判断是否合法
 * 超出时间限制
 */
public class NQueens_51 {
    private int[] subset;
    private List<List<String>> ans;
    private int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        subset = new int[n];
        ans = new ArrayList<>();
        dfs(0);
        return ans;
    }

    public void dfs(int index) {
        if (index == n) {
            System.out.println(Arrays.toString(subset) + ":" + isValid(subset));
            if (isValid(subset)) {
                addSubAns(subset);
            }
            return;
        }
        // 尝试四个位置
        for (int i = 0; i < n; i++) {
            subset[index] = i;
            dfs(index + 1);
        }
    }

    private void addSubAns(int[] subset) {
        List<String> set = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (j == subset[i]) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }

            }
            set.add(sb.toString());
        }
        ans.add(set);
    }

    private boolean isValid(int[] subset) {

        Map<Integer, Boolean> used1 = new HashMap<>();
        Map<Integer, Boolean> used3 = new HashMap<>();
        boolean[] used2 = new boolean[n];

        for (int i = 0; i < n; i++) {
            int j = subset[i];
            if (used1.containsKey(i + j) ||
                    used3.containsKey(i - j) ||
                    used2[subset[i]])
                return false;
            used1.put(i + j, true);
            used3.put(i - j, true);

            used2[j] = true;
        }
        return true;
    }

    public static void main(String[] args) {
        NQueens_51 test = new NQueens_51();
        //test.solveNQueens(4);
        test.n = 4;
        int[] subSet = new int[]{1, 3, 0, 2};

        System.out.println(test.isValid(subSet));
    }
}
